0522. 最长特殊序列 II【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 枚举 + 子序列判定

1. 📝 题目描述

• leetcode

给定字符串列表 strs，返回其中 最长的特殊序列 的长度。如果最长特殊序列不存在，返回 -1。

特殊序列 定义如下：该序列为某字符串 独有的子序列（即不能是其他字符串的子序列）。

s 的 子序列可以通过删去字符串 s 中的某些字符实现。

• 例如，"abc" 是 "aebdc" 的子序列，因为您可以删除"aebdc"中的下划线字符来得到 "abc"。"aebdc"的子序列还包括"aebdc"、 "aeb" 和 "" (空字符串)。

---

示例 1：

输入: strs = ["aba","cdc","eae"]
输出: 3

示例 2：

输入: strs = ["aaa","aaa","aa"]
输出: -1

---

提示：

• 2 <= strs.length <= 50
• 1 <= strs[i].length <= 10
• strs[i] 只包含小写英文字母

2. 🎯 s.1 - 枚举 + 子序列判定

c

bool isSub(char* a, char* b) {
    int i = 0, la = strlen(a), lb = strlen(b);
    for (int j = 0; j < lb && i < la; j++)
        if (a[i] == b[j]) i++;
    return i == la;
}

int findLUSlength(char** strs, int strsSize) {
    int res = -1;
    for (int i = 0; i < strsSize; i++) {
        int unique = 1;
        for (int j = 0; j < strsSize; j++) {
            if (i != j && isSub(strs[i], strs[j])) { unique = 0; break; }
        }
        if (unique) {
            int len = strlen(strs[i]);
            if (len > res) res = len;
        }
    }
    return res;
}

js

/**
 * @param {string[]} strs
 * @return {number}
 */
var findLUSlength = function (strs) {
  const isSub = (a, b) => {
    let i = 0
    for (let j = 0; j < b.length && i < a.length; j++) if (a[i] === b[j]) i++
    return i === a.length
  }
  let res = -1
  for (let i = 0; i < strs.length; i++) {
    let unique = true
    for (let j = 0; j < strs.length; j++) {
      if (i !== j && isSub(strs[i], strs[j])) {
        unique = false
        break
      }
    }
    if (unique) res = Math.max(res, strs[i].length)
  }
  return res
}

py

class Solution:
    def findLUSlength(self, strs: List[str]) -> int:
        def is_sub(a, b):
            it = iter(b)
            return all(c in it for c in a)
        res = -1
        for i, s in enumerate(strs):
            if all(i == j or not is_sub(s, strs[j]) for j in range(len(strs))):
                res = max(res, len(s))
        return res

• 时间复杂度：$O(n^2\times l)$，其中 $n$ 是字符串数量，$l$ 是字符串最大长度
• 空间复杂度：$O(1)$

算法思路：

• 对每个字符串，检查它是否是其它任何字符串的子序列
• 若不是任何其它字符串的子序列，则它是“特殊序列”
• 取所有特殊序列中的最大长度